1. Field of the Invention
The present invention generally relates to cache memory management in high performance data processing systems and, more particularly, to a means for reducing the cost of cache misses at context swap points by choosing points in time for swapping contexts when a program's footprint tends to be small.
2. Description of the Prior Art
In multi-programmed or multi-tasking computer systems, a processor is shared among many different programs by periodically changing the program or task that is running on the processor. For computing systems with cache memories, at the point that one program, or task, is suspended and another is begun, the cache contains many lines that belong to the suspended program. These lines will tend to be displaced from cache as subsequent programs run and will have to be reloaded when the suspended program regains control of the processor. The overhead for reloading those lines is called the cache-reload transient. D. F. Thiebaut and H. S. Stone in an article entitled "Footprints in the Cache" published in ACM Trans. on Computing, vol. 5, no. 4, Nov. 1987, at pages 305 to 329, report their studies of this problem and propose a model for calculating the size of the transient that they validated by several different case studies. The size of the transient is related to the size of the footprint of the program, which is the number of active lines that the program has in the cache.
It is known in the prior art to reduce the cost of context swaps by changing as little as possible, or by other means to reduce the overhead of the context swap. However, the prior art assumes that context swaps must be taken when a request for a swap is issued.
U.S. Pat. No. 4,422,145 to Sacco et al. describes the management of a pool of pages in buffer memory that takes advantage of knowledge of future requests for data. It uses this knowledge to hold the most likely future requests in the buffer pool where they can be retrieved quickly. It is intended to solve a problem of allocation of pages to tasks.
U.S. Pat. No. 4,463,424 to Mattson et al. describes an invention similar to that of Sacco et al., although it differs in detail. Mattson et al. measure task behavior to determine how to allocate memory to individual tasks so as to reduce the number of misses in cache memory. However, requests made to cache memory are honored in the order received.
U.S. Pat. No. 4,484,274 to Berenbaum et al. describes a procedure which identifies what part of the state of a process actually needs to be saved when an interrupt occurs. Hence, given that an interrupt is to be honored, it attempts to save as little as possible. U.S. Pat. No. 4,382,278 to Appelt teaches how to reduce context swap overhead by switching workspaces. This reduces the amount of work at a context swap. T. G. Lang in IBM Technical Disclosure Bulletin, July 1986, p. 947, describes a means for speeding the context swap by reducing some overhead associated with the process of saving context.